package longestcommonsubstring

// 找到两个字符串的最长公共子串（Longest Common Substring），可以使用动态规划（Dynamic Programming）的方法
func longestcommonsubstring(a, b string) string {
	// 创建一个二维数组来存储公共子串的长度
	dp := make([][]int, len(a)+1)
	for i := range dp {
		dp[i] = make([]int, len(b)+1)
	}

	maxLength := 0
	endIndex := 0

	// 填充动态规划表
	// dp[i][j] 表示 a[0:i] 和 b[0:j] 的最长公共子串的长度(此处是公共后缀的长度，而且i和j在此处表示的是长度，而不是下标)
	// 如果 a[i-1] == b[j-1]，则 dp[i][j] = dp[i-1][j-1] + 1
	// 否则 dp[i][j] = 0
	// 这里的 i 和 j 从 1 开始，因为 dp[0][*] 和 dp[*][0] 都初始化为 0
	// 这样可以避免边界条件的判断
	for i := 1; i <= len(a); i++ {
		for j := 1; j <= len(b); j++ {
			// 状态转移方程很简单，就是如果比我短一位的a和b的子串，各自延展1位的情况下，这1位恰好相等，那么当前两个串的公共子串长度就基于上一个+1就可以了
			// 也就是 dp[i][j] = dp[i-1][j-1] + 1
			if a[i-1] == b[j-1] {
				dp[i][j] = dp[i-1][j-1] + 1
				if dp[i][j] > maxLength {
					maxLength = dp[i][j]
					endIndex = i
				}
			}
		}
	}

	return a[endIndex-maxLength : endIndex]
}
